import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 74646
 * Date: 2022-03-15
 * Time: 12:35
 */
public class Topk {
    /**
     * 前K个最小的元素（需要创建大根堆，堆的大小为K）
     * @param array
     * @param k
     * @return
     */
    public static int[] topk(int[] array,int k){
        //创建一个大小为k的大根堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //遍历数组中的元素，将元素放入创建的堆中
        for(int i=0;i<array.length;i++){
            if(maxHeap.size()<k){
                maxHeap.offer(array[i]);
            }else{
                //从第k+1个元素开始，每个元素与堆顶元素进行比较
                int top = maxHeap.peek();
                if(top>array[i]){
                    maxHeap.poll();
                    maxHeap.offer(array[i]);
                }
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = maxHeap.poll();
        }
        return ret;
    }

    public  static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> minHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return o2.get(0)+o2.get(1) - o1.get(0) - o1.get(1);
            }
        });
        for (int i = 0; i < Math.min(nums1.length,k); i++) {
            for (int j = 0; j < Math.min(nums2.length,k); j++) {
                if(minHeap.size()<k){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    minHeap.offer(list);
                }else{
                    int top = minHeap.peek().get(0)+minHeap.peek().get(1);
                    if(top>nums1[i]+nums2[j]){
                        minHeap.poll();
                        List<Integer> list = new ArrayList<>();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        minHeap.offer(list);
                    }
                }
            }
        }
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < k && !minHeap.isEmpty(); i++) {
            ret.add(minHeap.poll());
        }
        return ret;
    }

    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        for (int i = 0; i < nums.length; i++) {
            if(priorityQueue.size()<k){
                    priorityQueue.offer(nums[i]);
            }else{
                int top = priorityQueue.peek();
                if(top<nums[i]){
                    priorityQueue.poll();
                    priorityQueue.offer(nums[i]);
                }
            }
        }
        return priorityQueue.poll();
    }

    public static void main(String[] args) {
        int[] nums1 = {1,1,2};
        int[] nums2 = {1,2,3};
        List<List<Integer>> ret = kSmallestPairs(nums1,nums2,2);
        System.out.println(ret);
    }
}
